1. Technical Field
The present invention generally relates to a distributed virtual environment in which the movement of an avatar controlled by a user is predicted. In particular, the present invention relates to a distributed virtual environment which is divided into zones wherein the likelihood of an avatar moving within a predetermined range of a zone boundary is predicted.
2. Description of Related Art
A virtual environment is a computer model of a three-dimensional space. At their most basic virtual environment applications allow a user to specify a “camera” location from which they wish to view the space. The application then renders the appropriate view of the environment from this location and presents it to the user on a monitor of the computer running the application. With this degree of functionality virtual environments can be used in a wide variety of visualisation applications e.g. taking a walk around a building not yet constructed.
Most virtual environment applications are however considerably more sophisticated than this and offer both an environment populated with objects (termed entities) which possess both a state and behaviour, and a means for the user to interact with these entities.
Virtual environments have many applications. One which has become particularly popular is in the field of computer games. Games such as Doom and Quake allow a user to control an entity to interact with the virtual environment modifying the state of entities within the virtual environment.
A further development of the virtual environment concept is the shared virtual environment. This involves a number of users, each with their own copy of the relevant virtual environment application (termed a client) experiencing a three dimensional space which is common to them all. Each user not only perceives the results of their interactions with the entities but also the results of other users interactions. To represent the location of a user in a shared virtual environment a special case of entity, known as an avatar is employed. This provides a visual representation on all of the clients as to where a particular user is viewing the scene from.
A shared virtual environment is usually implemented using a computer network wherein remote users operate clients in the network which incorporates servers for the virtual environment.
For simple virtual environments, where the number of entities is limited, implementing a shared version is comparatively straightforward. As each user joins the virtual environment a client is provided with the current state of all entities within it. As the environment state changes, due to either user invoked behaviour or autonomous behaviour, the newly generated state information is distributed to all clients, allowing a common view between different clients to be maintained.
However, for larger virtual environments, where both the number of simultaneous users and entities is large, this approach breaks down. This is because the amount of information required to supply and support a total-description of state at each client overwhelms either the network connection of the client or the processing power available to the client.
One common solution to this problem is to utilise the fact that a client does not need to maintain a valid state description of any entities its user is unaware of. For example, if two avatars are playing tennis, it is important that both their clients are kept fully informed of the position of the ball. However, for the users who can't see or hear the tennis court it is not necessary to inform them of either the ball state or the state of the avatars playing tennis. Only when they move into a position where the court can be observed is this information required.
A common implementation of this solution sub-divides the environment into a number of regions, termed zones and then groups the entities on the basis of the zone they occupy. Each users avatar location is then used to assess what zones the user is aware of, and the client is informed of the state of all entities within these zones. As entities update their state they broadcast the change only to the clients aware of their current zone. In this way the network and processing load on each client is proportional to the state changes in their avatars surrounding location, rather than the total environment.
An example of an implementation of this type of this approach is NPSNET (Macedonia et al. “NPSNET: A Network Software Architecture for Large Scale Virtual Environments”, Presence, Volume 3, No. 4, Fall 1994) the content of which is hereby incorporated by reference. In this implementation the virtual environment is divided into a number of hexagonal zones and a multicast address is associated with each zone. Each client maintains a network connection to the multicast address of the zone its avatar is in. This address is used by the client to broadcast any avatar state change e.g. movement. Additionally the client also maintains network connections to the multicast address of any zones the user is aware of i.e. within visual or aural range. Hence two clients with neighbouring avatars will share avatar state updates by virtue of using common multicast addresses. However, two users widely separated within the virtual environment will not share awareness of any zones and hence will not load each others network connection with shared state information.
FIG. 1 is an illustration of this zonal distributed virtual environment. As can be seen in FIG. 1 an avatar has a range of awareness which comprises a volume which is often spherical and is centred on an avatar. This range of awareness encloses all the entities that a client needs to possess the state of in order to accurately display the world to the user. The volume is often defined with respect to the visual range of any rendering performed at the client although it may be derived from the range of any of the relevant senses e.g. hearing.
In FIG. 1 the illustrated area of the virtual environment is divided into nine geographic areas or zones each of which has a multicast address associated with it. Client A has an avatar A in zone 3 and has a range of awareness which spans into zones 2 and 6. Thus, client A monitors zones 2, 3 and 6. Since the avatar A can modify the state of entities in zone 3, and since the avatar state changes, updates are made using the multicast address for zone 3. Avatar B has a visual range which encompasses zone 3 and client B therefore listens to zone 3's multicast address as well as zone 2's multicast address in which the avatar B is present. Therefore, any changes to avatar A will be detected by client B and similarly any changes to avatar B will be detected by client A. In contrast, avatar C has no visual awareness of zones 2 or 3 and therefore client C does not listen to their multicast addresses. This reduces the network load.
FIG. 2 is a schematic diagram of a network hosting the virtual environment schematically illustrated in FIG. 1. Nine servers (1-9) are illustrated interconnected by a communications network 10 such as a local area network (LAN) or a wide area network (WAN). Each server is responsible for a respective geographical zone in the virtual environment and receives and transmits the status of the zone using a unique multicast address assigned for the zone. Also connected to the communications network 10 are three clients, client A (11), client B (12) and client C (13). Each client hosts an avatar and thus maintains the virtual environment experienced by the avatar. As described above each client will connect to a multicast address i.e. to a server dependent upon the zones of which an avatar is aware. A client can either comprise a workstation or an application i.e. a computer program running on a computer. Thus a single computer may host more than one client. Similarly a server can either comprise a dedicated computer or an application i.e. a computer program running on a computer. Thus a single computer may host more than one server.
In an alternative arrangement disclosed in our copending Application No. GB 9722343.2 filed on 22 Oct. 1997, the content of which is hereby incorporated by reference, zone managers are responsible for managing each zone within the virtual environment and thus the location of the avatar within the virtual environment and the awareness range of the avatar will determine the communications required between the client and the zone managers.
In this arrangement objects in the virtual environment have a conceptual model, a dynamics model and a visual model. A rule manager is associated with the conceptual model. The visual model is provided at each client and the dynamic model is associated with the zone managers. Thus only dynamics information needs to be passed between the zone managers and the clients.
A problem identified by the inventors in a zoned distributed environment is how to link avatar movement to zone awareness. FIG. 3 illustrates this problem. Avatar A is in zone 1 and moving towards the boundary between zone 1 and zone 2. Client A is therefore aware of the state of the entities within zone 1 (entities 1 and 2) but is unaware of the state of any of the entities within zone 2 (entities 3 and 4). At some point in the future, avatars A awareness will overlap into zone 2 and client A must become fully informed of the state of all entities in zone 2 (entities 3 and 4).
If client A only starts to fetch the initial state of the entities in zone 2 at the point avatar A becomes initially aware of zone 2 i.e. the awareness region touches the boundary between zones 1 and 2, a number of problems can arise:
1. Graphical inconsistency. While the initial state of the zone is being fetched the avatar may continue moving towards it. Hence the avatar may be in the visual range of entities which have not yet been supplied. When the initial state download is complete these entities will suddenly appear, giving a visual glitch.
2. User control problems. If the avatar is prevented from moving whilst fetching the state of a zone (in an effort to prevent the graphical inconsistency described above), it will reduce the interactive nature of the client user interface.
3. State Inconsistency. If the avatar is moving fast enough it may even cross into the next zone before its client has a full description of all the relevant entities. This could lead to the client trying to make invalid state settings. For example, placing the avatar in the middle of a wall because at the time the avatar moved the client was unaware of the wall entity.